The present invention relates to generation apparatus that is shift register generator based in apparatus for storing or transmission of data.
A symbol herein is a representation of one or more signals. Humans are good at processing characters, symbols signs and images. Devices and apparatus working under control of a processor are well suited to process signals. In common language, it is often expressed that machines such as computers process and store symbols and images. This is an anthropomorphism that is incorrect. Computing devices are switching machines that change switching states based on a state or property of a signal. While it may appear that a machine “knows” what it is doing, it really doesn't. This may appear to be a philosophical issue, but in the context of the requirements of a U.S. patent disclosure, it is not. While a symbol is something that is associated with humans, related to computing devices a symbol is a representation of a signal. Furthermore, a symbol in human terms can be any of a set of symbols, characters of an alphabet, algebraic or mathematical symbols, pictograms, pixel or digits in a numbering system. A machine, currently, for processing requires a translation or an assignment of a symbol into a pre-defined signal, usually within fairly tight specifications, before it can process the signals in accordance with the assigned meaning of symbols. For instance a symbol such as a letter in an alphabet, such as ‘q’, in general in binary processing, is to be translated in a series of bits, for instance a byte of 8 bits. While one applies the term bit, it is well understood in the art that a bit is also a defined signal.
For instance the letter ‘q’ may be entered from a keyboard, by pressing a key bearing the letter ‘q’ as a sign for humans. It is to be understood that this assignment of meaning is to a certain level arbitrary. The lower case ‘q’ in ASCII is assigned code 113. The signals representing 113 should be used consistently to represent ‘q’. However, internal to a computing device no letter ‘q’ exists, only signals in a byte that represent the value 113 in the binary case.
Symbols herein thus have at least one of 2 states and often have more than 2 states. If a signal consists of 8 bits or binary signals it can be interpreted as a 256-state signal. Devices such as D/A converters can be used to convert 8 bits into a single signal that can have 256 states. A signal state can be a signal level such as a voltage or light intensity or any other phenomenon that has one of n occurrences. However, the state can also be a physical property that is not related to its intensity or magnitude. For instance a state of a signal can be a frequency or wavelength or any other phenomenon, including a position or elative position, the presence of a material, a quantum-mechanical state and any other phenomenon that can be distinguished from another one. QAM signals are for instance an example of mixed state signals, wherein relative angle and amplitude define a state space. Accordingly one can actually have multiple physical phenomena to represent a single state of an n-state signal.
The signal may be an electric signal, an optical signal, a biological signal, an acoustical signal, a mechanical signal, a presence of a materials or a change in a state of a material such as a change of a quantum-mechanical state or any other phenomenon that indicates a state or a change of state. In addition, a symbol can represent a single signal. For instance a bit can be represent a signal that can have one of 2 states, like on or off for an electrical signal. A symbol can also represent a plurality of symbols that by itself represent a higher order symbol. As mentioned before, a character can be one of 256 symbols, which is a representation of 8 binary signals.
By using A/D and D/A converters one can convert and process n-state signals as binary words in accordance with n-state switching tables, but provide true n-state signals on an output. In one embodiment a general computer is a device to receive, to process and to generate an n-state signal such as a 3-state, a 4-state an 8-state a 256-state or any state signal that fits within the processing capability of the general computer that is further provided with A/D and D/A converters. The general has a processor and a memory. The computer has loaded and activated the computer application Matlab®, marketed by the Mathworks, Inc. of Natick, Mass. The active screen in Matlab is called the command window that is displayed on a display screen of the computer and is responsive to a command, which may be activated from a memory as a scripted program or via commands provided from a keyboard. One can enter from the keyboard the command: sc2=[0 1;1 0]. This causes an addressable matrix or table sc2 to be stored in memory. The addresses are formed by the indices originated from 1 and up for the position of rows and columns in the matrix. That first row of the matrix is [0 1] and the second row is [1 0]. The first column is
         [                            0                                      1                      ]  and the second column is
               [                                    1                                                0                              ]        .  To address the matrix and generate an output, the command sc2(1,2) may be provided. This generates the element of the matrix in the first row and second column of sc2, which is a 1.
One of ordinary skill will recognize that the matrix sc2 is the truth table of the binary logic function XOR. There appears to be a mismatch between the states of the truth table and the applied index system. One is reminded that binary states as displayed are merely symbols that are derived from actual signals. Each of the signals that are applied clearly has to be binary. That is, each address of the matrix sc2 is (a,b) wherein ‘a’ and ‘b’ are binary symbols, each symbol being represented by or being a representation of a signal. Matlab works with matrices in origin 1. That is each index for a matrix in Matlab address starts at 1. In binary logic one commonly uses the logic states True/False; On/Off or 1/0. Binary logic or switching logic is commonly used to describe switching devices. In its earliest use this was disclosed by Claude Shannon in his M.S. Thesis: A Symbolic Analysis of Relay and Switching Circuits dated by stamp on Dec. 20, 1940 at MIT and signed by Claude Shannon on Aug. 10, 1937. (see <<www.cs.virginia.edu/˜robins/Shannon_MS_Thesis.pdf>>. This thesis document is incorporated herein by reference.
What is clear from this and other known documents is that the symbols 0 and 1 used in the context of switching and computer technology represent “logic values” which are human interpretations of underlying real physical phenomena or physical states or signals. While it is common to mention states 0 and 1 with relation to computers these symbols 0 and 1 represent real physical states. These symbols are used in computer arithmetic to seemingly represent numbers in a radix-2 representation. This is for human convenience. There is no physical reason to use the symbols 0 and 1 to represent the actual physical states or signals. The binary states can also be called 1 and 2. By doing that a symbol representing an input signal also is part of an index identifying an output state of the matrix sc2. This is called using representation in origin 1. After generating a resulting switching state determined by the switching table sc2 the device then provides the resulting state as a signal on an output. This output signal can be provided on a channel for transmission or on an input for further processing by yet another switching device, or it is provided on a memory for storage.
In the exemplary embodiment of the present invention with a computer the output is connected to a display screen and the output signal activates pixel elements on the screen to display a symbol. The matrix sc2 is activated by entering in the command window via the keyboard of the computer in Matlab the statement sc2=[1 2;2 1] followed by a=2 and b=1. By typing sc2(a,b) the computer outputs and displays the symbol 2 on the screen. The keyboard has over 40 keys, which each can be activated mechanically. Each key on the keyboard has a different position. Each key, when activated generates one or more signals that uniquely corresponds to that key. Accordingly, the keys with marks 1 and 2 represent signals, when activated, which has one of 2 states. The output symbol on the screen (which in accordance with sc2 can be 1 or 2) represents a signal which has one of two states. Accordingly, the computer as described implements a physical device that is described by a binary switching table.
The computer running Matlab operates in origin 1. Other programming languages such as APL run in origin 0 and use the symbols 0 and 1 as proper input and output symbols. The switching tables are also origin 0.
The computer running Matlab in a further embodiment of the present invention are configured to run and implement 3-state switching devices, for instance by activating matrix sc3=[1 2 3;2 3 1;3 1 2] or matrix sc4=[1 2 3 4;2 3 4 1;3 4 1 2;4 1 2 3] or any other n-state matrix that is used as a switching device. One dimensional matrices or vectors are used to implement inverters such as: inv2=[2 1]; inv3=[3 2 1], inv=[4 3 2 1] or any other inverter.
The above describes how generic computers or processors with memories are configured as a specific switching device that implement or realize an n-state switching device with n=2 or n>2. Other realizations or implementations of n-state switching devices are possible. One can use binary combinational switching devices of which the XOR, NAND, AND, OR, NOR, INVERTER and other gates are known. With these circuits any other binary and non-binary switching table can be realized. If needed A/D and D/A converters can be applied, though a word of 2 or more bits is specifically considered to be an n-state signal. An addressable memory such as a RAM, ROM, PROM, EPROM, magnetic, opto-electronic, quantum-mechanical, or any other storage or memory device can be used to store and retrieve states of an n-state switching table. If needed A/D and D/A converters are used if the memory/storage device only stores binary signals.
Embodiments of the present invention apply switching functions that are also called logic functions. These functions represent devices that generate one or more signals based on one or more input signals, wherein the signals for the purpose of description are represented by one or more symbols.
Storage and/or transmission of signals require sometimes a minimum amount of transitions between signal states. One reason is to assist clock recovery circuitry to extract sufficient information to generate a correct clock signal. In other applications there is a need for security. For instance, an information carrying signal stream is reversibly combined with a stream of random like signals to hide the information signal stream from unauthorized reading. In yet other applications one may want to discover if a signal stream is tampered with.
Linear Feedback Shift Registers (LFSRs) are known and are applied in applications such as sequence generators, scramblers, coders, descramblers and decoders. However, sequences generated by LFSRs are believed to be more easily detected and reconstructed by cryptanalysis than for instance sequences generated by non-linear feedback shift register (NLF/SR) based sequence generators.
Shift registers are known devices. They are available as electronic components as a true serial shift register such as the Serial-in to Parallel-out (SIPO)-Serial-in to Serial-out (SISO)-Parallel-in to Serial-out (PISO) and Parallel-in to Parallel-out (PIPO) shift registers, generally under control of a clock signal, but some operating asynchronously. Shift register chips are for instance available from Texas Instruments of Dallas, Tex. and may come in different technologies such as CMOS or TTL with clock speeds well over 10 MHz to over 100 MHz. Non-binary symbol representing shift registers can be formed from using shift register chips connected in parallel wherein a word of bits distributed over several chips forms a word that represents a non-binary symbol that is shifted.
Shift registers are also formed from RAM and are for instance available as a shift register IP core for Field Programmable Gate Arrays and are available from Altera Corporation, of San Jose, Calif.
Shift registers can also be programmed into a programmable processor with access to memory by applying store, retrieve and shift operations. The content of such programmed shift register devices is available or can be updated externally through available I/O ports.
Furthermore, shift registers can be created from individual flip-flops or latches. Non-binary memory elements that can be applied in non-binary shift registers are disclosed in U.S. Pat. No. 7,397,690 issued to Lablans on Jul. 8, 2008 which is incorporated herein by reference.
All non-binary switching devices represented by n-valued switching functions can at least be realized in binary device with required A/D converters at an input and a D/A converter at an output. While the term switching or logic function and n-state, symbols (binary or nonbinary) are used it is to be understood that a symbol is a representation of a signal and a switching or logic function represents a switching device.
The processing of signals represented by symbols takes place at a speed of at least 1000 symbols per second, preferably at a speed of at least 1 million symbols per second and most preferably with a speed of at least 100 million symbols per second. Only machines achieve this processing speed. No human can process symbols at these required speeds. Furthermore, humans cannot process signals as required herein.
The literature asserts that sequences generated by binary shift registers containing only linear feedback functions are easier to detect than sequences generated by sequence generators having also non-linear functions, such as the AND function.
Accordingly, sequences generated by novel and improved devices and methods that cannot be implemented by linear functions only, are required.